﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{
    public class Solution221
    {
        public int MaximalSquare1(char[][] matrix)//暴力肯定超时
        {//遍历边长和左上角
            int m = matrix.Length;
            int n = matrix[0].Length;
            int maxLen = Math.Min(m, n);
            int res = 0;

            Console.WriteLine(m);
            Console.WriteLine(n);
            for (int row = 0; row < m; row++)
            {
                for (int col = 0; col < n; col++)
                {
                    for (int l = 1; l <= maxLen; l++)
                    {
                        if (row + l <= m && col + l <= n)
                        {
                            bool isSqure = MyTest(matrix, row, col, l);
                            Console.WriteLine(isSqure);
                            if (isSqure)
                            {
                                res = Math.Max(res, l * l);
                            }
                        }
                    }
                }
            }
            return res;
        }

        private bool MyTest(char[][] matrix, int row, int col, int len)
        {
            for (int i = 0; i < len; i++)
            {
                for (int j = 0; j < len; j++)
                {
                    if (matrix[row + i][col + j] != '1')
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        public int MaximalSquare2(char[][] matrix)//动态规划,实际上也是暴力，因为重复算了很多
        {
            int m = matrix.Length;
            int n = matrix[0].Length;
            int maxLen = Math.Min(m, n);
            int res = 0;
            bool[][][] dp = new bool[m][][];
            for (int i = 0; i < m; i++)
            {
                dp[i] = new bool[n][];
                for (int j = 0; j < n; j++)
                {
                    dp[i][j] = new bool[maxLen + 1];
                    dp[i][j][0] = true;
                }
            }

            for (int l = 1; l <= maxLen; l++)
            {
                for (int row = 0; row < m; row++)
                {
                    for (int col = 0; col < n; col++)
                    {
                        if (row + l <= m && col + l <= n)
                        {
                            if (dp[row][col][l - 1])//小正方形满足
                            {
                                bool isSqure = NextSquare(matrix, row, col, l);
                                Console.WriteLine(isSqure);
                                if (isSqure)//大正方形满足
                                {
                                    dp[row][col][l] = true;
                                    res = Math.Max(res, l * l);
                                }
                            }
                        }
                    }
                }
            }
            return res;
        }

        private bool NextSquare(char[][] matrix, int row, int col, int l)
        {
            //检测最后一行和最后一列是不是1
            int lastrow = row + l - 1;
            int lastcol = col + l - 1;
            //最后一行
            for (int i = col; i <= lastcol; i++)
            {
                if (matrix[lastrow][i] != '1')
                {
                    return false;
                }
            }
            //最后一列
            for (int i = row; i <= lastrow; i++)
            {
                if (matrix[i][lastcol] != '1')
                {
                    return false;
                }
            }
            return true;
        }

        public int MaximalSquare(char[][] matrix)//真正的动态规划
        {
            int m = matrix.Length;
            int n = matrix[0].Length;
            int maxLen = Math.Min(m, n);
            int res = 0;
            int[][] dp = new int[m][];//以右下角（i，j)开始的正方形的边长
            for (int i = 0; i < m; i++)
            {
                dp[i] = new int[n];
            }

            for (int row = 0; row < m; row++)
            {
                for (int col = 0; col < n; col++)
                {
                    //只有左上，左，上，三个都是正方形，这个才可以＋1
                    if (matrix[row][col] == '1')
                    {
                        if (row - 1 >= 0 && col - 1 >= 0)
                        {
                            dp[row][col] = Math.Min(dp[row][col - 1], Math.Min(dp[row - 1][col], dp[row - 1][col - 1])) + 1;
                        }
                        else//row=0
                        {
                            dp[row][col] = 1;//边上的肯定为1
                        }
                    }
                    res = Math.Max(res, dp[row][col]);
                }
            }
            return res * res;
        }
    }

    internal class Program221
    {
        private static void Main221(string[] args)
        {
            char[][] matrix = [['1']];
            Solution221 solution = new Solution221();
            int res = solution.MaximalSquare(matrix);
            Console.WriteLine(res);
        }
    }
}